package com.gxc.array;

/**
 *
 41. 缺失的第一个正数
 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 */
public class FirstMissingPositive {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{1,2,0}));
        System.out.println(handle(new int[]{3,4,-1,1}));
        System.out.println(handle(new int[]{7,8,9,11,12}));
        System.out.println(handle(new int[]{2}));
        System.out.println(handle(new int[]{1}));
    }

    /**
     * 对于数组长度为n的数组，缺失的第一个正数  必定在1.。。n+1 之间
     * @param nums
     * @return
     */
    public static int handle(int[] nums) {
        int l = nums.length;
        for (int i = 0; i < l; i++) {
            if (nums[i] > l) nums[i] = l+1;
            else if (nums[i]<0) nums[i] = 0;
        }

        int i = 0;
        while (i < l) {
            while (nums[i]!= l+1 && nums[i]>0 && nums[i]!= i+1) {
                if (nums[i] == nums[nums[i]-1]) {
                    nums[i] = 0;
                    break;
                }
                swap(nums, i, nums[i]-1);
            }
            i++;
        }
        for (int j = 0; j < l; j++) {
            if (nums[j] != j+1) return j+1;
        }
        return l+1;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 哈希表
     */
    class Solution {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= 0) {
                    nums[i] = n + 1;
                }
            }
            for (int i = 0; i < n; ++i) {
                int num = Math.abs(nums[i]);
                if (num <= n) {
                    nums[num - 1] = -Math.abs(nums[num - 1]);
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] > 0) {
                    return i + 1;
                }
            }
            return n + 1;
        }
    }

    /**
     * 置换
     */
    class Solution2 {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return n + 1;
        }
    }


}
